from typing import List


class Solution:
    """
    方法：回溯法
    Args: digits (str): 包含数字2-9的字符串
    Returns: List[str]: 所有可能的字母组合
    Time: O(N4^N)，其中 n 为 digits 的长度。最坏情况下每次需要枚举 4 个字母，递归次数为一个满四叉树的节点个数，
    那么一共会递归 O(4^N) 次（等比数列和），再算上加入答案时复制 path 需要 O(N) 的时间，所以时间复杂度为 O(N4^N)
    Space: O(N + M)，用于存储递归调用栈和当前路径
    """
    def letterCombinations(self, digits: str) -> List[str]:
        n = len(digits)
        if n == 0:
            return[]
        MAPPING = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        ans = []
        path = [''] * n
        def backtrack(i):
            if i == n:
                ans.append(''.join(path))
                return
            for c in MAPPING[int(digits[i])]:
                path[i] = c
                backtrack(i + 1)
        backtrack(0)
        return ans